package com.c2b.algorithm.leetcode.base;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 左叶子之和
 * <p>给定二叉树的根节点 root ，返回所有左叶子之和。
 * <p>注意这里只要叶子节点</>
 *
 * @author c2b
 * @since 2022/5/20 9:27
 */
public class LC0404sumOfLeftLeaves {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return process1(root);
    }

    /**
     * 深度优先遍历
     *
     * @param root 根节点
     * @return int 所有左叶子的值相加和
     * @author c2b
     * @since 2022/5/20 10:16
     */
    private int process1(TreeNode root) {
        int result = 0;
        // 判断是否有左节点
        if (root.left != null) {
            // 如果左子节点为叶子节点，加上值即可
            // 如果左子节点不是叶子节点，带着当前值继续找左子节点
            result += isLeave(root.left) ? root.left.val : process1(root.left);
        }
        // 判断是否有右子节点,并且右子节点不是叶子节点
        if (root.right != null && !isLeave(root.right)) {
            // 带着当前值去找左子节点 和 右子节点的最左叶子节点
            result += process1(root.right);
        }
        return result;
    }


    /**
     * 宽度优先遍历
     *
     * @param root 根节点
     * @return int 所有左叶子的值相加和
     * @author c2b
     * @since 2022/5/20 10:16
     */
    private int process2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        int result = 0;
        // 对于队列中的每一个元素来说，
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 如果有左节点，并且左节点是叶子节点,计数。否则加入队列中等下一次判断
            if (node.left != null) {
                if (isLeave(node.left)) {
                    result += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            // 如果有右节点，并且右节点不是叶子节点,加入队列中。等下一次判断
            if (node.right != null && !isLeave(node.right)) {
                queue.offer(node.right);
            }
        }
        return result;
    }

    /**
     * 判断节点是否为叶子节点
     *
     * @param treeNode 树节点
     * @return boolean true是叶子节点 false不是叶子节点
     * @author c2b
     * @since 2022/5/20 10:04
     */
    private boolean isLeave(TreeNode treeNode) {
        return treeNode.right == null && treeNode.left == null;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.right = new TreeNode(7);
        System.out.println(new LC0404sumOfLeftLeaves().sumOfLeftLeaves(treeNode));
        HashMap<Integer, Integer> map = new HashMap();
    }
}
